1. Field of the Invention
The present invention relates to an apparatus for rendering 3D (three-dimensional) graphics data and more particularly to an apparatus and method for reconstructing 3D graphics data.
2. Description of the Related Art
A VRML (Virtual Reality Modeling Language), MPEG (Moving Picture Expert Group) standards, and a file format defined by a general commercial program (e.g., 3D Studio Max, Maya, etc.) are used by an apparatus for rendering 3D graphics data on a screen. 3D data includes: geometric information (e.g., information about positions of 3D points constituting an object and connection information thereof) of an object positioned in 3D space; material information of an object (e.g., information about texture, transparency of an object, color of an object, and shininess of an object's surface); and information about change of such information depending on position, characteristics of a light source, and time. Such 3D graphics data is expressed with a structure intuitively or logically understandable so that a user may easily generate and modify the graphics data. An object in which 3D graphics data is expressed with a structure intuitively understandable in this manner is called a scene graph.
FIG. 1 is a diagram illustrating an example of a node structure of a scene graph. As shown in FIG. 1, the scene graph stores 3D graphic data in a plurality of nodes (group nodes and shape nodes). The group nodes have information about sub-nodes and the shape nodes are leaf nodes and store geometric information and/or material information of an object. In particular, the scene graph includes: nodes that include geometric information and/or material information of an object and connection information that forms a hierarchy by connecting the nodes. Also, some information including position information and rotational information of the node influences position of the sub-nodes. The strong point of such a structure is that its subordinate relationship is easy for a person to understand intuitively according to the relative positions of the nodes.
FIG. 2 is a scene graph of a 3D human body structure. As shown in FIG. 2, suppose that a body of a “person” is expressed in the 3D space. With an abstract node “person” used as a starting node, a “person” is roughly divided into “chest” and “stomach” parts, and the “chest” and the “stomach” are sub-nodes of the node “person”. Also, sub-nodes of the “chest” include a “head,” a “right arm” and a “left arm,” and sub-nodes of the “stomach” include a “left leg” and a “right leg”. Information in a high ranking node has a direct influence on a sub-node. Therefore, if position information of the node “person” is changed, such position change information directly influences each of the sub-nodes. Thus, to change the whole body information of a “person” generated in the 3D space, only the relevant information in the node “person” needs to be changed. Such a structure is very convenient and intuitive from the viewpoint of a user who generates and modifies 3D data, because, as described above, only information of the node “person”, the highest ranking node, needs to be modified when moving the entire body, not the position information of each part of the body. Also, when changing part of the body information, only the information of the relevant node needs to be changed, without changing information in the sub-nodes.
To read in such 3D graphics data and output the same to a screen, an apparatus for analyzing the meaning of the read 3D graphics data and performing data conversion, is required. Generally, such an apparatus is called a 3D graphics rendering engine. The 3D graphics rendering engine includes a parser and a renderer.
The parser reads in and interprets 3D graphics data. Namely, the parser identifies whether the read data is geometric information of an object, material information of an object, or information about a subordinate relationship between objects originated from the scene graph structure, and interpreting and judging the information.
The renderer changes the scene graph parsed by the parser into a form appropriate for display on a screen of an output device. Since a screen is appropriate for displaying 2D information, the 3D scene graph cannot be directly used. A primary role of the renderer is to convert 3D graphics data into 2D graphics data by performing a coordinate transformation on an object expressed in 3D space. Therefore, output data from the renderer is converted into 2D graphics data.
However, a problem with such a conventional 3D graphics rendering engine lies in producing a 2D output image by performing a 2D data conversion process only on 3D graphics data without changing a 3D graphics data structure. The scene graph, which is a method for expressing a data structure of the 3D graphic data, is an easy structure that can be easily understood and modified intuitively by a user as described above, but storage space is wasted, generation of an output image is delayed, and image quality of the output image is deteriorated. As shown in FIG. 2, there exist nodes that include the same kinds of material information and such nodes are arranged in a discontinuous and irregular order. The renderer converts 3D graphics data of each node into 2D data without changing the scene graph's structure.
FIG. 3 is a diagram illustrating an order of data conversion of the scene graph shown in FIG. 2. Referring to FIG. 3, even if the same kind of material information appears repeatedly, the renderer cannot be aware of such information during the rendering process. Therefore, the renderer repeatedly stores all material information appearing according to a predetermined order in a data storage space on a terminal. Therefore, when using the conventional 3D graphics rendering engine, waste of storage space occurs.
Also, when material information changes between two neighboring nodes during the rendering process, the renderer throws away the original material information and reads the new material information into the storage space of the terminal. Generally, since the process of reading and/or writing data from and to the storage space requires more time compared to other processes such as mathematical computation, such information change causes a large delay in the whole process of converting 3D information into 2D information. Since the conventional 3D graphics rendering engine always reads material information due to a discontinuous arrangement of the same material information, the generation of an output image is delayed.
Also, information representing transparency of an object may be included in the information held by the 3D graphics data. When the nodes having this information are arranged in a discontinuous and irregular order, exact conversion of 3D information into 2D information cannot be guaranteed. When 3D objects having a transparent property are positioned in an overlapping manner, conversion of 3D information into 2D information should be performed by reflecting characteristics such as transparency and the distance of other 3D objects existing in the viewing frustum. However, since the conventional 3D graphics rendering engine does not reflect transparency and distance between 3D objects that belong to each node when determining a rendering order, deterioration in image quality of an output image occurs.